Constraint-based path computation is a fundamental building block for traffic engineering systems, such as Multiprotocol Label Switching (MPLS) and Generalized Multiprotocol Label Switching (GMPLS) networks. Performing path computation in large, multi-domain, multi-region, or multi-layer networks can be quite complex and may require special computational components and cooperation between the different network domains.
One existing approach to the path computation problem involves the use of a Path Computation Element (PCE)-based model. The PCE-based model includes a PCE entity that is capable of computing a network path or route based on a network graph. The PCE is an application that can be located within a network node or component or on an out-of-network server.
Multiple PCEs can be used to compute inter-domain shortest constrained paths across a predetermined sequence of domains using a backward-recursive path computation technique. The backward-recursive path computation technique relies on communication between cooperating PCEs. In particular, a path computation client (PCC) sends a request to a PCE in its domain. The request is forwarded between PCEs, domain-by-domain, until the PCE responsible for the domain containing the LSP destination (i.e., the destination domain) is reached. The PCE in the destination domain creates a tree of potential paths to the destination (referred to as a Virtual Shortest Path Tree or VSPT) and passes the VSPT back to the previous PCE. Each PCE, in turn, adds to the VSPT and passes the VSPT back until the PCE in the source domain uses the VSPT to select an end-to-end path that the PCE sends to the PCC.